home *** CD-ROM | disk | FTP | other *** search
/ Aminet 1 (Walnut Creek) / Aminet - June 1993 [Walnut Creek].iso / usenet / sources / volume90 / aplictns / route_10 / part02 / board.c < prev    next >
C/C++ Source or Header  |  1990-04-23  |  6KB  |  255 lines
  1. #include <stdio.h>
  2.  
  3. /*
  4. #ifndef M_XENIX
  5. #include <stdlib.h>
  6. #endif
  7. */
  8.  
  9. #include "cell.h"
  10.  
  11. #define LIMIT    0x10000        /* 64k */
  12.  
  13. /* board dimensions */
  14. int Nrows = ILLEGAL;
  15. int Ncols = ILLEGAL;
  16.  
  17. int InitBoardDone = 0; /* sanity check */
  18.  
  19. /* memory usage */
  20. long Ltotal = 0; /* for board */
  21. long Itotal = 0; /* for dist */
  22. long Ctotal = 0; /* for dir */
  23.  
  24. /*
  25. ** memory is allocated in blocks of rows. as many rows as will fit in 64k are
  26. ** allocated in each block. blocks are linked together by pointers. the last
  27. ** block has a null 'next' pointer. if you want to route some *really* big
  28. ** boards (so big that 640k is not sufficient), you should change the
  29. ** algorithms below to test for Lotus-Intel-Microsoft expanded memory (LIM 3.2
  30. ** or 4.0) and use it if present. this would be a major enhancement, so if you
  31. ** do it i hope you will send it back to me so that it can be incorporated in
  32. ** future versions.
  33. */
  34.  
  35. struct lmem { /* a block of longs */
  36.     struct lmem *next;     /* ptr to next block */
  37.     long         mem[1]; /* more than 1 is actually allocated */
  38.     };
  39.  
  40. struct imem { /* a block of ints */
  41.     struct imem *next;     /* ptr to next block */
  42.     int         mem[1]; /* more than 1 is actually allocated */
  43.     };
  44.  
  45. struct cmem { /* a block of chars */
  46.     struct cmem *next;     /* ptr to next block */
  47.     char         mem[1]; /* more than 1 is actually allocated */
  48.     };
  49.  
  50. struct lhead { /* header of blocks of longs */
  51.     int         numrows; /* number of rows per block */
  52.     struct lmem *side[2]; /* ptr to first block of each chain */
  53.     };
  54.  
  55. struct ihead { /* header of blocks of ints */
  56.     int         numrows; /* number of rows per block */
  57.     struct imem *side[2]; /* ptr to first block of each chain */
  58.     };
  59.  
  60. struct chead { /* header of blocks of chars */
  61.     int         numrows; /* number of rows per block */
  62.     struct cmem *side[2]; /* ptr to first block of each chain */
  63.     };
  64.  
  65. static struct lhead Board = { 0, {NULL,NULL} }; /* 2-sided board */
  66. static struct ihead Dist = { 0, {NULL,NULL} }; /* path distance to cells */
  67. static struct chead Dir = { 0, {NULL,NULL} }; /* pointers back to source */
  68.  
  69. extern int justboard;
  70.  
  71. extern char *Alloc();
  72.  
  73. void InitBoard();
  74. long GetCell();
  75. void SetCell();
  76. void OrCell();
  77. int GetDist();
  78. void SetDist();
  79. int GetDir();
  80. void SetDir();
  81.  
  82. void InitBoard () { /* initialize the data structures */
  83.     long lx, ly; /* for calculating block sizes */
  84.     struct lmem **ltop;     /* for building board chain */
  85.     struct lmem **lbottom;     /* for building board chain */
  86.     struct imem **itop;     /* for building dist chain */
  87.     struct imem **ibottom;     /* for building dist chain */
  88.     struct cmem **ctop;     /* for building dir chain */
  89.     struct cmem **cbottom;     /* for building dir chain */
  90.     int r, c, i, j, k; /* for calculating number of rows per block */
  91.  
  92.     InitBoardDone = 1; /* we have been called */
  93. /* allocate Board (longs) */
  94.     for (lx = (long)Ncols*sizeof(long), ly = 0, i = 0;
  95.         i < Nrows && ly <= LIMIT - sizeof(long *); ly += lx, i++)
  96.         ; /* calculate maximum number of rows per block */
  97.     Board.numrows = --i;
  98.     ltop = &(Board.side[TOP]);
  99.     lbottom = &(Board.side[BOTTOM]);
  100.     for (j = Nrows; j > 0; j -= i) {
  101.         k = (j > i) ? i : j;
  102.         ly = ((long)k * lx) + sizeof(long *);
  103.         *ltop = (struct lmem *)Alloc( ly );
  104.         *lbottom = (struct lmem *)Alloc( ly );
  105.         Ltotal += 2*ly;
  106.         ltop = (struct lmem **)(*ltop);
  107.         lbottom = (struct lmem **)(*lbottom);
  108.         }
  109.     *ltop = *lbottom = NULL;
  110.     if (!justboard) {
  111. /* allocate Dist (ints) */
  112.         for (lx = (long)Ncols*sizeof(int), ly = 0, i = 0;
  113.             i < Nrows && ly <= LIMIT - sizeof(int *);
  114.             ly += lx, i++)
  115.             ; /* calculate maximum number of rows per block */
  116.         Dist.numrows = --i;
  117.         itop = &(Dist.side[TOP]);
  118.         ibottom = &(Dist.side[BOTTOM]);
  119.         for (j = Nrows; j > 0; j -= i) {
  120.             k = (j > i) ? i : j;
  121.             ly = ((long)k * lx) + sizeof(int *);
  122.             *itop = (struct imem *)Alloc( ly );
  123.             *ibottom = (struct imem *)Alloc( ly );
  124.             Itotal += 2*ly;
  125.             itop = (struct imem **)(*itop);
  126.             ibottom = (struct imem **)(*ibottom);
  127.             }
  128.         *itop = *ibottom = NULL;
  129. /* allocate Dir (chars) */
  130.         for (lx = (long)Ncols*sizeof(char), ly = 0, i = 0;
  131.             i < Nrows && ly <= LIMIT - sizeof(char *);
  132.             ly += lx, i++)
  133.             ; /* calculate maximum number of rows per block */
  134.         Dir.numrows = --i;
  135.         ctop = &(Dir.side[TOP]);
  136.         cbottom = &(Dir.side[BOTTOM]);
  137.         for (j = Nrows; j > 0; j -= i) {
  138.             k = (j > i) ? i : j;
  139.             ly = ((long)k * lx) + sizeof(char *);
  140.             *ctop = (struct cmem *)Alloc( ly );
  141.             *cbottom = (struct cmem *)Alloc( ly );
  142.             Ctotal += 2*ly;
  143.             ctop = (struct cmem **)(*ctop);
  144.             cbottom = (struct cmem **)(*cbottom);
  145.             }
  146.         *ctop = *cbottom = NULL;
  147.         }
  148. /* initialize everything to empty */
  149.     for (r = 0; r < Nrows; r++) {
  150.         for (c = 0; c < Ncols; c++) {
  151.             SetCell( r, c, TOP, (long)EMPTY );
  152.             SetCell( r, c, BOTTOM, (long)EMPTY );
  153.             if (!justboard) {
  154.                 SetDist( r, c, TOP, EMPTY );
  155.                 SetDist( r, c, BOTTOM, EMPTY );
  156.                 SetDir( r, c, TOP, EMPTY );
  157.                 SetDir( r, c, BOTTOM, EMPTY );
  158.                 }
  159.             }
  160.         }
  161.     }
  162.  
  163. long GetCell( r, c, s ) /* fetch board cell */
  164.     int r, c, s;
  165.     {
  166.     struct lmem *p;
  167.  
  168.     p = Board.side[s];
  169.     while (r >= Board.numrows) {
  170.         p = p->next;
  171.         r -= Board.numrows;
  172.         }
  173.     return( p->mem[r*Ncols+c] );
  174.     }
  175.  
  176. void SetCell( r, c, s, x ) /* store board cell */
  177.     int r, c, s;
  178.     long x;
  179.     {
  180.     struct lmem *p;
  181.  
  182.     p = Board.side[s];
  183.     while (r >= Board.numrows) {
  184.         p = p->next;
  185.         r -= Board.numrows;
  186.         }
  187.     p->mem[r*Ncols+c] = x;
  188.     }
  189.  
  190. void OrCell( r, c, s, x ) /* augment board cell */
  191.     int r, c, s;
  192.     long x;
  193.     {
  194.     struct lmem *p;
  195.  
  196.     p = Board.side[s];
  197.     while (r >= Board.numrows) {
  198.         p = p->next;
  199.         r -= Board.numrows;
  200.         }
  201.     p->mem[r*Ncols+c] |= x;
  202.     }
  203.  
  204. int GetDist( r, c, s ) /* fetch distance cell */
  205.     int r, c, s;
  206.     {
  207.     struct imem *p;
  208.  
  209.     p = Dist.side[s];
  210.     while (r >= Dist.numrows) {
  211.         p = p->next;
  212.         r -= Dist.numrows;
  213.         }
  214.     return( p->mem[r*Ncols+c] );
  215.     }
  216.  
  217. void SetDist( r, c, s, x ) /* store distance cell */
  218.     int r, c, s, x;
  219.     {
  220.     struct imem *p;
  221.  
  222.     p = Dist.side[s];
  223.     while (r >= Dist.numrows) {
  224.         p = p->next;
  225.         r -= Dist.numrows;
  226.         }
  227.     p->mem[r*Ncols+c] = x;
  228.     }
  229.  
  230. int GetDir( r, c, s ) /* fetch direction cell */
  231.     int r, c, s;
  232.     {
  233.     struct cmem *p;
  234.  
  235.     p = Dir.side[s];
  236.     while (r >= Dir.numrows) {
  237.         p = p->next;
  238.         r -= Dir.numrows;
  239.         }
  240.     return( (int)(p->mem[r*Ncols+c]) );
  241.     }
  242.  
  243. void SetDir( r, c, s, x ) /* store direction cell */
  244.     int r, c, s, x;
  245.     {
  246.     struct cmem *p;
  247.  
  248.     p = Dir.side[s];
  249.     while (r >= Dir.numrows) {
  250.         p = p->next;
  251.         r -= Dir.numrows;
  252.         }
  253.     p->mem[r*Ncols+c] = (char)x;
  254.     }
  255.